package lanqiao._02算法训练.page03;

import java.util.Scanner;

/**
 * @author 挚爱之夕
 * @version 1.0
 * @implSpec 问题描述
 * 　　斐波那契串由下列规则生成：
 * 　　F[0] = "0";
 * 　　F[1] = "1";
 * 　　F[n] = F[n-1] + F[n-2] （n≥2，+表示连接）
 * 　　给出一个由0和1构成的串S和一个数n，求出F[n]中S出现的次数。
 * 输入格式
 * 　　第一行一个数n
 * 　　第二行一个01串S
 * 输出格式
 * 　　答案
 * 样例输入
 * 96
 * 10110101101101
 * 样例输出
 * 7540113804746346428
 * 数据规模和约定
 * 　　n≤2^63^-1，子串长≤10000，答案≤263-1
 * f[0] = 0
 * f[1] = 1
 * f[2] = 10
 * f[3] = 101
 * f[4] = 10110
 * f[5] = 10110101
 * @since 2022 - 12 - 22 - 9:42
 */
public class _23斐波那契串 {
}

class Main23 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        String s = sc.next();
        if(s.equals("0")){
            return;
        }else if(s.equals("1")){
            return;
        }
        int cur = 2;
        String[] f = new String[2];
        f[0] = "0";
        f[1] = "1";
        //找第一个包含s的字符串 f[cur]
        while (cur <= n) {
            f[cur % 2] = f[(cur - 1) % 2] + f[(cur - 2) % 2];
            if (f[cur % 2].contains(s)) break;
            cur++;
        }
        if(cur > n){
            System.out.println(0);
        }else{
            //F(n) = F(n-1) + F(n-2) + 1
            get(cur - 1, n);
        }
    }
    static void get(long m, long n) {
        long a = 0;
        long b = 1;
        for (long j = m; j <= n; j++) {
            long t = b;
            b += a;
            a = t;
        }
        System.out.println(b - 1);
    }
}

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = Long.parseLong(sc.nextLine());
        String s = sc.nextLine();
        String pre = "0";
        StringBuilder cur = new StringBuilder("1");
        if (s.compareTo("0") == 0) {
            System.out.println(adds(0, n));
        } else if (s.compareTo("1") == 0) {
            System.out.println(adds(1, n));
        }
        for (int i = 0;  i < n; i++) {
            String tmp = cur.toString();
            cur.append(pre);
            pre = tmp;
            if (pre.contains(s)) {
                System.out.println(adds(i, n));
                break;
            }
        }
    }

    //继续菲波那切数列规律进行计算
    public static long adds(long m, long n) {
        long a = 0;
        long b = 1;
        for (long j = m; j <= n; j++) {
            long t = b;
            b += a;
            a = t;
        }
        return b - 1;
    }
}
